//#include <iostream>
//
//using namespace std;
//const int N = 1e5 + 10;
//
//int n, q;
//int a[N];
//
//int first(int x) {
//	int left = 0, right = n-1;
//	while (left < right) {
//		int mid = (left + right) / 2;
//		if (a[mid] < x) left = mid + 1;
//		else right = mid;
//	}
//	if (a[left] >= x) return left;
//	else return -1;
//}
//int last(int x) {
//	int left = 0, right = n-1;
//	while (left < right) {
//		int mid = (left + right + 1) / 2;
//		if (a[mid] > x) right = mid - 1;
//		else left = mid;
//	}
//	if (a[left] <= x) return left;
//	else return -1;
//}
//
//int main()
//{
//	cin >> n;
//	for (int i = 0; i < n; i++) cin >> a[i];
//
//	cin >> q;
//	while (q--) {
//		int l, r;
//		cin >> l >> r;
//		int left = first(l);
//		int right = last(r);
//		if (left == -1) cout << 0 << endl;
//		else cout << right - left + 1 << endl;
//	}
//
//	return 0;
//}
